package leetcode.code0098;

import leetcode.helper.tree.TreeNode;

public class Solution extends Solution98 {

	@Override
	public boolean isValidBST(TreeNode root) {
		return this.isBST(root)[0] == 1 ? true : false;
	}

	// ans[0]==0 子树不是搜索树 ans[0]==1 子树是搜索树
	// ans[1] 子树最小值
	// ans[2] 子树最大值
	private int[] isBST(TreeNode root) {
		TreeNode left = root.left;
		TreeNode right = root.right;
		int cur = root.val;
		int curMin = cur;
		int curMax = cur;
		int[] ans = new int[] { 0 };// false
		if (left != null) {
			if (left.val >= cur) {// 当前左树不满足
				return ans;
			}
			int[] leftAns = this.isBST(left);
			if (leftAns[0] == 0 || leftAns[2] >= cur) {// 左子树不满足 or 左子树的最大值不满足
				return ans;
			}
			curMin = leftAns[1];
		}
		if (right != null) {
			if (right.val <= cur) {// 当前右树不满足
				return ans;
			}
			int[] rightAns = this.isBST(right);
			if (rightAns[0] == 0 || rightAns[1] <= cur) {// 当前右子树不满足 or 右子树最小值不满足
				return ans;
			}
			curMax = rightAns[2];
		}
		return new int[] { 1, curMin, curMax };// 都满足
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
